package myself.a015Dp;


/**
 * @author 叶之越
 * Description
 * Date 2021/2/2
 * Time 14:11
 * Mail 739153436@qq.com
 */
public class RobotWalk {
    // 机器人走路问题
    // 第一步：暴力递归实现
    // N代表最大长度，start代表起始位置，aim代表目标位置，K代表剩余步数
    public static int ways1(int N, int start, int aim, int K) {
        if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
            return -1;
        }
        return process1(start, K, aim, N);
    }

    private static int process1(int cur, int k, int aim, int fin) {
        if (k == 0) {
            return cur == aim ? 1 : 0;
        }
        if (cur == 1) {
            return process1(cur + 1, k - 1, aim, fin);
        }
        if (cur == fin) {
            return process1(cur - 1, k - 1, aim, fin);
        }
        return process1(cur + 1, k - 1, aim, fin) + process1(cur - 1, k - 1, aim, fin);
    }

    // 第二步：暴力递归优化
    public static int ways2(int N, int start, int aim, int K) {
        if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
            return -1;
        }
        int[][] cache = new int[N + 1][K + 1];
        for (int i = 0; i < cache.length; i++) {
            for (int j = 0; j < cache[i].length; j++) {
                cache[i][j] = -1;
            }
        }
        return process2(start, K, aim, N, cache);
    }

    private static int process2(int cur, int k, int aim, int fin, int[][] cache) {
        if (cache[cur][k] >= 0) {
            return cache[cur][k];
        }
        int ans = 0;
        if (k == 0) {
            ans = cur == aim ? 1 : 0;
        } else if (cur == 1) {
            ans = process2(cur + 1, k - 1, aim, fin, cache);
        } else if (cur == fin) {
            ans = process2(cur - 1, k - 1, aim, fin, cache);
        } else {
            ans = process2(cur + 1, k - 1, aim, fin, cache) + process2(cur - 1, k - 1, aim, fin, cache);
        }
        cache[cur][k] = ans;
        return ans;
    }

    // 第三步：实现真正dp
    public static int ways3(int N, int start, int aim, int K) {
        if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
            return -1;
        }
        int[][] cache = new int[N + 1][K + 1];
        cache[aim][0] = 1;
        for (int i = 1; i < cache[0].length; i++) {
            cache[1][i] = cache[2][i - 1];
            for (int j = 1; j < N; j++) {
                cache[i][j] = cache[i - 1][j - 1] + cache[i + 1][j + 1];
            }
            cache[N][i] = cache[N - 1][i - 1];
        }
        return process2(start, K, aim, N, cache);
    }
}
